Apabila Malaysia (terdahulunya Malaya) memohon untuk menyertai Pertubuhan Bangsa-Bangsa Bersatu pada tahun 1957, Belanda adalah salah satu negara yang mengundi "ya" semasa panggilan untuk kemasukan ahli-ahli baru, menjadikan Persekutuan Tanah Melayu menjadi ke-82 ahli Pertubuhan Bangsa-bangsa Bersatu.[2] Walaupun penubuhan hubungan diplomatik antara kedua negara bermula pada tahun yang sama, Malaysia hanya menubuhkan Kedutaan Besarnya di Den Haag pada September 1966. Ia berpindah ke bangunan tetap di Rustenburgweg pada musim panas tahun 1985.